/*
 * @lc app=leetcode.cn id=42 lang=golang
 *
 * [42] 接雨水
 */

// 6. 动态规划
// @lc code=start
func trap(height []int) (ans int) {
	n := len(height)
	if n == 0 {
		return
	}

	leftMax := make([]int, n)
	leftMax[0] = height[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}

	rightMax := make([]int, n)
	rightMax[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}

	for i, h := range height {
		ans += min(leftMax[i], rightMax[i]) - h
	}
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

// @lc code=end

// 5. 单调栈
// @lc code=start
func trap(height []int) (ans int) {
	stack := []int{}
	for i, h := range height {
		for len(stack) > 0 && h > height[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}
			left := stack[len(stack)-1]
			curWidth := i - left - 1
			curHeight := min(height[left], h) - height[top]
			ans += curWidth * curHeight
		}
		stack = append(stack, i)
	}
	return
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

// @lc code=end

// 4. 双指针 对3的优化
// left从左向右遍历，right从右向左遍历
// 对left来说，leftMax一定准确，rightMax不一定准确
// 但是left的rightMax一定 >= right的rightMax（已知条件）
// 所以只要 leftMax < rightMax ，（leftMax - height[left]）就是left棒子的接水量
// right 同理
// @lc code=start
func trap(height []int) (ans int) {
	left, right := 0, len(height)-1
	leftMax, rightMax := -1, -1
	for left < right {
		leftMax = max(leftMax, height[left])
		rightMax = max(rightMax, height[right])

		if leftMax < rightMax {
			ans += leftMax - height[left]
			left++
		} else {
			ans += rightMax - height[right]
			right--
		}
	}
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 3. 双指针 对2的优化
// @lc code=start
func trap(height []int) (ans int) {
	leftMax := 0
	left := make([]int, len(height))
	for i := 0; i < len(height); i++ {
		leftMax = max(leftMax, height[i])
		left[i] = leftMax
	}

	rightMax := 0
	right := make([]int, len(height))
	for i := len(height) - 1; i >= 0; i-- {
		rightMax = max(rightMax, height[i])
		right[i] = rightMax
	}

	for i := 0; i < len(height); i++ {
		ans += min(left[i], right[i]) - height[i]
	}
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

// @lc code=end

// 2. 暴力 不超时
// 枚举每根棒子，各找到左右两边最长的棒子，然后拿到这两根棒子中短的一根
// 减去当前棒子的棒子就是能接到的水量
// @lc code=start
func trap(height []int) (ans int) {
	for i := 0; i < len(height); i++ {
		leftMax, rightMax := 0, 0
		for j := i; j >= 0; j-- {
			leftMax = max(leftMax, height[j])
		}

		for j := i; j < len(height); j++ {
			rightMax = max(rightMax, height[j])
		}
		ans += min(leftMax, rightMax) - height[i]
	}
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

// @lc code=end

// 1. 不知道叫啥，用例全部通过
// @lc code=start
func trap(heights []int) int {
	left, right, res1 := 0, 1, 0
	for right < len(heights) {
		if heights[left] >= heights[right] {
			res1 += heights[left] - heights[right]
			right++
		} else {
			left = right
			right++
		}
	}
	left, right = len(heights)-2, len(heights)-1
	res2 := 0
	for left >= 0 {
		if heights[right] >= heights[left] {
			res2 += heights[right] - heights[left]
			left--
		} else {
			right = left
			left--
		}
	}

	// 虽然绕点，但结局还是好的
	whiteAndWater := len(heights)*maxArr(heights) - sum(heights)
	whiteAnd2Water := res1 + res2
	return whiteAnd2Water - whiteAndWater
}

func sum(arr []int) int {
	val := 0
	for i := 0; i < len(arr); i++ {
		val += arr[i]
	}
	return val
}

func maxArr(arr []int) int {
	maxVal := 0
	for i := 0; i < len(arr); i++ {
		maxVal = max(maxVal, arr[i])
	}
	return maxVal
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end